import java.util.Arrays;

public class Offer40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr,0,arr.length-1,k);
    }

    public int[] quickSort(int[] arr, int l, int r,int k) {
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr,i,j);
        }
        swap(arr,i,l);
        if (i>k) return quickSort(arr,l,i-1,k);
        if (i<k) return quickSort(arr,i+1,r,k);
        return Arrays.copyOf(arr,k);
    }
    public void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        Offer40 offer40 = new Offer40();
        int[] a=new int[]{0,1,2,1};
        offer40.getLeastNumbers(a,1);
    }
}
